package Leetcode.数组字符串;

import java.util.*;

/**
 * @ClassName 字符串中的查找与替换
 * @since: 2023/8/15 14:03
 * @auth: kirito
 * @description:
 * https://leetcode.cn/problems/find-and-replace-in-string/
 *
 * 在字符串 s 中根据给定的索引位置，将对应的源字符串 sources 替换为目标字符串 targets，
 * 生成最终的结果字符串。代码通过遍历字符串，
 * 并检查索引位置是否需要进行替换操作，
 * 根据源字符串和目标字符串进行替换或保持原始字符。
 **/
public class 字符串中的查找与替换 {
    public static String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int n = s.length(); // 输入字符串的长度
        int m = indices.length; // 替换操作的数量

        // 创建一个映射表，用于存储每个索引位置需要进行替换的源字符串和目标字符串的对应关系
        Map<Integer, List<Integer>> ops = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < m; ++i) {
            ops.putIfAbsent(indices[i], new ArrayList<Integer>());
            ops.get(indices[i]).add(i);
        }
        StringBuilder ans = new StringBuilder(); // 存储最终结果的字符串构建器
        for (int i = 0; i < n; ) {
            boolean succeed = false;
            if (ops.containsKey(i)) { // 如果当前位置需要进行替换操作
                for (int pt : ops.get(i)) {
                    // 检查当前位置开始的子串是否与源字符串相等
                    if (s.substring(i, Math.min(i + sources[pt].length(), n)).equals(sources[pt])) {
                        succeed = true;
                        ans.append(targets[pt]); // 添加目标字符串到结果中
                        i += sources[pt].length(); // 更新索引位置
                        break;
                    }
                }
            }
            if (!succeed) { // 如果没有成功进行替换操作，则将原始字符添加到结果中
                ans.append(s.charAt(i));
                ++i;
            }
        }
        return ans.toString(); // 返回最终结果的字符串
    }

    public static String findReplaceString2(String s, int[] indices, String[] sources, String[] targets) {
        int n = s.length(); // 输入字符串的长度
        String[] replaceStr = new String[n]; // 存储替换后的字符串
        int[] replaceLen = new int[n]; // 存储被替换的长度
        Arrays.fill(replaceLen, 1); // 默认无需替换时 i+=1

        // 遍历索引和源字符串数组，进行替换操作
        for (int i = 0; i < indices.length; i++) {
            int idx = indices[i]; // 当前索引位置
            if (s.startsWith(sources[i],idx)) { // 如果从当前索引位置开始的子串与源字符串相等
                replaceStr[idx] = targets[i]; // 存储目标字符串
                replaceLen[idx] = sources[i].length(); // 存储被替换的长度
            }
        }

        StringBuilder ans = new StringBuilder(); // 存储最终结果的字符串构建器
        for (int i = 0; i < n; i += replaceLen[i]) { // 根据被替换的长度更新索引位置
            if (replaceStr[i] == null) { // 如果没有替换字符串，则将原始字符添加到结果中
                ans.append(s.charAt(i));
            } else { // 如果有替换字符串，则将替换字符串添加到结果中
                ans.append(replaceStr[i]);
            }
        }
        return ans.toString(); // 返回最终结果的字符串
    }


    public static void main(String[] args) {
        String s = "abcd";
        int[] indices = {0, 2};
        String[] sources = {"a", "cd"};
        String[] targets = {"eee", "ffff"};

        String result = findReplaceString2(s, indices, sources, targets);
        System.out.println(result);
    }
}
